#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 55; // 最大导弹数量

int n;             // 导弹数量
int heights[MAXN]; // 导弹高度数组
int ans = MAXN;    // 最小系统数量，初始化为导弹数量的最大值

// 深度优先搜索函数
// idx: 当前考虑的导弹索引
// up: 上升系统中的最后一个导弹高度
// down: 下降系统中的最后一个导弹高度
void dfs(int idx, vector<int> &up, vector<int> &down)
{
    if (up.size() + down.size() >= ans)
        return; // 剪枝，如果当前系统数量已经超过最优解，直接返回
    if (idx == n)
    {
        ans = min(ans, static_cast<int>(up.size() + down.size()));
        return;
    }

    // 尝试将当前导弹添加到上升系统中
    int k = 0;
    while (k < up.size() && up[k] >= heights[idx])
        k++;
    if (k < up.size())
    {
        int temp = up[k];
        up[k] = heights[idx];
        dfs(idx + 1, up, down);
        up[k] = temp;
    }
    else
    {
        up.push_back(heights[idx]);
        dfs(idx + 1, up, down);
        up.pop_back();
    }

    // 尝试将当前导弹添加到下降系统中
    k = 0;
    while (k < down.size() && down[k] <= heights[idx])
        k++;
    if (k < down.size())
    {
        int temp = down[k];
        down[k] = heights[idx];
        dfs(idx + 1, up, down);
        down[k] = temp;
    }
    else
    {
        down.push_back(heights[idx]);
        dfs(idx + 1, up, down);
        down.pop_back();
    }
}

int main()
{
    while (cin >> n && n)
    {
        for (int i = 0; i < n; i++)
        {
            cin >> heights[i];
        }
        ans = MAXN;
        vector<int> up, down;
        dfs(0, up, down);
        cout << ans << endl;
    }
    return 0;
}